#include <vector>
#include <string>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <list>
using namespace std;

// 只出现一次的数字
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (int e : nums)
        {
            ret ^= e;
        }
        return ret;
    }
};

// 只出现一次的数字II
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++)
        {
            int n = 0;
            for (int e : nums) n += (e >> i) & 1;
            if (n % 3) ret |= ((n % 3) << i);
        }
        return ret;
    }
};

// 只出现一次的数组III
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long n = 0;
        for (int e : nums) n ^= e;
        int lowbit = n & -n;
        vector<int> v(2);
        for (int e : nums) v[(e & lowbit) == 0] ^= e;
        return v;
    }
};

// 比特位计数
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ret;
        for (int i = 0; i <= n; i++)
        {
            int sum = 0;
            int n = i;
            while (n)
            {
                n &= (n - 1);
                sum++;
            }
            ret.push_back(sum);
        }
        return ret;
    }
};

// 判断字符是否唯一
class Solution {
public:
    bool isUnique(string astr) {
        if (astr.size() > 26) return false;
        int bitmap = 0;
        for (auto ch : astr)
        {
            int i = ch - 'a';
            if ((bitmap >> i) & 1) return false;
            else bitmap |= (1 << i);
        }
        return true;
    }
};

// 丢失的数字
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = 0;
        for (int e : nums) ret ^= e;
        for (int i = 0; i <= nums.size(); i++) ret ^= i;
        return ret;
    }
};